1. Field of the Invention
The present invention relates to a method of block matching computing for image processing, and particularly relates to a method of multi-path block matching computing for image processing and a method of block matching computing utilizing a flat pattern.
2. Description of the Prior Art
Motion estimation utilizing a block matching processing is usually applied to many video encoding technique standards, such as ITU-T, H. 261, H. 263, ISO MPEG-1, MPEG-2 and MPEG-4. Such video encoding techniques are used for solving repetition of continuous frames in the time domain. Compared with the compression technique for a single frame (i.e. JPEG), such video encoding techniques include higher compression efficiency. Besides video compression, motion estimation can further be used for motion tracing, video noise filtering and object separating of a non-fixed camera. Motion estimation requires a lot of computing, however, so various kinds of high-speed block matching methods are developed, which are used for substantially decreasing the complexity of calculation under the condition of tolerant error. The methods for decreasing computing complexity can be divided into two categories. A first category decreases the searching points in a searching pattern to approach the best solution gradually. Such a kind of method includes decreasing the pixel number of block sampling or utilizing matching rules with low complexity. Some examples of high-speed block matching methods and methods for decreasing the number of block sampling are described below.
Most high-speed block matching methods utilize a searching pattern and range to determine the searching process. For continuous images of real world, motion vectors of most objects are non-existent or slight, and a few are fast. Thus, the motion vector always has the distribution characteristic of center-bias, which is used for a 3-step-searching method, and a 4-step-searching method and gradient searching method are used for improving the efficiency of the 3-step-searching method. The searching patterns of the above-mentioned methods are based on a square shape. Furthermore, the diamond searching method utilizes searching patterns with closer and fewer searching points. In this way, the diamond searching method not only increases the searching speed, but also decreases the probability of limiting the local optimum solution.
A hexagon searching method utilizes a hexagon searching pattern with seven checking points, and further adds 3 checking points for each searching step. For frames with high DPI (dots per inch), the hexagon searching method is not as accurate as the diamond searching method, and although it has a higher speed, it has a poor accuracy for video with low DPI. A cross diamond searching method utilizes a cross searching pattern at first, and then utilizes halfway-stop technique and diamond searching patterns, thus it can achieve a faster speed than the diamond searching method while maintaining a searching quality that is similar to the diamond searching method. It utilizes different searching patterns and processing steps, however, thus involving higher cost and complexity.
Additionally, since scientific apparatus and semiconductors are rapidly improving, utilizing improved PC clocks can also increase the operation speed. The expansion of CPU media commands is advantageous for vision calculation, thus digital image processing and video compression are widely applied to PCs. Therefore, a digital video recorder includes several advantages such as: no distortion during repeated recording, ease of data backup, quick searching ability for data history and convenience of looking up. Multi monitoring at the same time is always a necessary demand for modern monitoring systems, but this function will cause heavy loading to the system. Also, the CPU will have a heavier loading if other functions such as noise filtering, invasion detecting, motion tracing, moving object identification and calculation, terrorist and behavior analyzing, fire detection, and watermarking encryption are required. Therefore, since it is desirable to have more sources for executing more vision functions, operation speed becomes an important factor for the monitoring system. Moreover, video compression will be widely applied in mobile phone systems in the future, and motion estimation occupies the greatest calculation power of the whole system. Therefore, low power calculation is necessary for modern high-speed motion estimation, but a single high-speed motion estimation method is not sufficient for real time multi recording of DVR, or real time application of other video compression methods. Accordingly, a faster block matching calculation method that can be applied with the method for sampling part of the pixels in the block is more suitable for a system that requires real time video processing. It should be noted that, since the high-speed block matching calculation method and the method for sampling part of pixels in the block cause distortion, such a combination may cause more distortion, which decreases the compression rate of the DVR system. Furthermore, there will be more demand for more channels, thus a new motion estimation technique with higher speed and low distortion is needed.
The following description summarily discloses the prior art 3 step searching method, diamond searching method, cross diamond searching method and the advantages and disadvantages of said methods.
Step 1 of the 3 step searching method computes a center point and a further 9 points that are 4 units away from the center point. Step 2 utilizes the point with a minimum pixel difference value from step 1 as the center point, computes points 2 units away from the center, and compares these pixel points to obtain a pixel point having a minimum pixel value difference. Step 3 utilizes the point having a minimum pixel difference value from step 2 as the center point, computes points 1 unit away from the center, and calculates nine points including the center to determine the point having a minimum pixel difference.
Such kind of method includes nine points and performs a searching operation from large range to small range. The correct motion vector will not be found, however, if the large range searching cannot find the correct direction at first. Since the 3 step searching method generally determines the location of the motion vector in step 1, the above-mentioned situation often happens, resulting in a non-accurate motion vector, but the 3 step searching method has the advantage of stable calculation.
The diamond searching method also includes 3 steps as described below: Step 1: Check and compute nine pixel points based on the center point of the searching range and determine if the point having a minimum pixel value difference is the center point. If yes, jump to step 3, otherwise continue with step 2. Step 2: Check and compute the pixels of the nine points of the diamond searching pattern based on the pixel having minimum block distortion from step 1 and determine if the point having a minimum pixel value difference is the center point. If yes, jump to step 3, otherwise repeat step 2. Step 3: Mark five diamond searching points based on the center point of the searching range and obtain the motion vector according to the point having minimum block distortion.
The diamond searching method utilizes non-rectangular searching, which includes the characteristic of centralizing searching close to the motion vector. Also, the diamond searching method utilizes a searching pattern with fewer searching points for a final check, and has a faster searching speed. Moreover, such kind of searching method utilizes repeated searching points to prevent the searched motion vector from being trapped into the local region. Since the method includes repeated searching points, it utilizes more overhead, however.
The cross diamond searching method includes the following steps: Step 1: Utilize the center point of the searching pattern as the start point and a cross pattern as the searching pattern to calculate nine pixels and determine if the point having a minimum pixel value difference is at the center of the searching pattern. If yes, the original point is the desired motion vector. If not, jump to step 2. Step 2: Increase two check points at the searching direction for minimum distortion value of step 1. If the location of the point with minimum distortion value is still at the center of the two new points, the co-ordinate is the motion vector. If not, jump to step 3. Step 3: Perform the diamond searching method by utilizing the point having a minimum pixel value from step 2 as the center point. The following steps are the same as the diamond searching method.
Practical video data includes a high probability in both horizontal and vertical directions. Thus, the cross diamond searching method is a diamond-searching-method-based calculation method of computing the cross pattern center point by utilizing such characteristics and the half-stop technique. It improves the accuracy and the speed while the motion vector is near the center. This method includes the most-complicated algorithm, however, and is hard to be realized. Furthermore, this method is slower than the diamond searching method and decreases the effect of said method while the motion vector occurs in areas not including the cross pattern
As described above, the prior searching method includes at least one of the following disadvantages: low speed, complicated computing, and low accuracy. Additionally, the above mentioned searching method only performs a searching operation based on pixels having a minimum pixel difference, however, the points excepting the point having a minimum pixel difference may also lie in the correct searching direction, thus the error probability for pattern searching is increased. Furthermore, the prior art searching method always suffers the problem of hollowing, that is, there is a high ratio of hollow pixels in the searching patterns, thus the accuracy is affected and the overhead is wasted.
Thus, a new searching method is needed to solve those problems mentioned above.